package MyDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * ip地址 IP地址复原 dfs
 */
public class Leetcode0093 {

    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int len = s.length();
        if(len<=3 || len>13){
            return res;
        }
        char[] ip = s.toCharArray();
        dfs(ip, s, len, "",0, 0, res);
        return res;
    }
    public static void dfs(char[] ip, String s, int len, String cur, int cur_index, int cnt, List<String> res){
        if(cnt == 4 && cur_index == len){
            System.out.println(cur);
            res.add(cur);
            return;
        }
        if(cnt > 4 || (cnt < 4 && cur_index == len)){
            return;
        }

        // 处理前置0
        if(ip[cur_index] == '0'){
            // 处理第一个字符串的小数点
            String tmp_str = (cnt == 0 ? cur + "0" : cur + ".0");
            dfs(ip, s, len, tmp_str,cur_index+1, cnt+1, res);
        }else {
            int tmp = 0;
            for(int idx= cur_index; idx<=cur_index + 2 && idx<len; idx++){
               tmp = tmp * 10 + ip[idx] - '0';
               if(tmp<=255){
                   String tmp_str = (cnt == 0 ? cur + s.substring(cur_index,idx+1) : cur + "." + s.substring(cur_index,idx+1));
                   dfs(ip, s, len, tmp_str, idx+1, cnt+1, res);
               }
            }
        }

    }

    public static void main(String[] args) {
        String aa = "101023";
        restoreIpAddresses(aa);
        System.out.println(aa.substring(1,3));
    }
}
